package com.example.leetcode.prcatice;

import java.util.Arrays;

public class Test1774 {

    private int r = Integer.MAX_VALUE;

    private int target = Integer.MAX_VALUE;

    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        this.target = target;
        for (int b:baseCosts) {
            dfs(toppingCosts,b,0);
            if (r == target) {
                return r;
            }
        }
        return r;
    }

    private void dfs(int[] toppingCosts,int total,int index) {
        // 判断成本价和最优解的关系
        int sign = Math.abs(r - target) - Math.abs(total - target);
        if (sign > 0 || (sign == 0 && total < r)) {
            r = total;
        }

        if (total >= target || index == toppingCosts.length) {
            return;
        }
        for (int i = 0;i<3;i++) {
            dfs(toppingCosts,total + toppingCosts[index] * i,index + 1);
        }
    }

    public int closestCost2(int[] baseCosts, int[] toppingCosts, int target) {
        // 冰淇淋基料的最小值min，
        int min = Arrays.stream(baseCosts).min().getAsInt();
        // 其他任何方案成本只会比min更大，与target的插值更大，此时直接返回min
        if (min >= target) {
            return min;
        }
        // 只需要考虑成本在 [min, upper-1] 间的方案是否存在
        int upper = 2 * target - min;
        boolean[] dp = new boolean[upper];
        // base，基料必选
        for (int baseCost : baseCosts) {
            // 不考虑区间外的方案
            if (baseCost < upper) {
                dp[baseCost] = true;
            }
        }
        // dp迭代，在基料的基础上选择辅料
        for (int toppingCost : toppingCosts) {
            // 倒序遍历dp
            for (int j = upper - 1; j >= min; --j) {
                // 每种辅料可以1份或两份，更新对应的dp为true，区间外不予考虑
                if (dp[j] && (j + toppingCost < upper)) {
                    dp[j + toppingCost] = true;
                }
                if (dp[j] && (j + 2 * toppingCost < upper)) {
                    dp[j + 2 * toppingCost] = true;
                }
            }
        }
        // 在 [min, upper-1]所有存在的方案种找出与target最接近的方案
        int ans = min;
        for (int i = min + 1; i < upper; ++i) {
            if (dp[i]) {
                // 更接近
                if (Math.abs(i - target) < Math.abs(ans - target)) {
                    ans = i;
                    // 同样接近，选择更小成本
                } else if (Math.abs(i - target) == Math.abs(ans - target)) {
                    ans = Math.min(ans, i);
                }
            }
        }
        return ans;
    }



}
